import numpy as np


def dminIndex(dist, K):
    index = 0
    dmin = dist[0]
    for j in range(K):
        if dmin > dist[j]:
            dmin = dist[j]
            index = j
    return dmin, index


def dmaxIndex(Mat, K):
    index = 0
    dmax = Mat[0]
    for i in range(K):
        if dmax < Mat[i]:
            dmax = Mat[i]
            index = i
    return dmax, index


def localSVD(X):
    row, col = np.shape(coeff)
    U, sigma, coeff = np.linalg.svd(X)

    maxarr = []
    absCoff = abs(coeff)

    for i in range(col):
        T = absCoff[:, i]
        dmax, index = dmaxIndex(T, row)
        maxarr.append(dmax)
    colsign = np.sign(maxarr)
    coeff = coeff * colsign

    return U, sigma, coeff

 
def MyKMean(data ,K ,iniCentriods ,iterations): 

    numOfData, numOfAttr = np.shape(data)
    c, t = np.shape(iniCentriods)
    
    centroids = iniCentriods.copy()
    pre_centroids = iniCentriods.copy()
    ##
    for iter in range(iterations):
        tags = np.zeros((numOfData, K))
        ## Ѱģ
        for i in range(numOfData):
            D = np.zeros((K))
            Dist = D
            # ÿ㵽ÿĵı׼
            for j in range(K):
                DT = data[i, :]
                CT = centroids[j,:]
                N = data[i,:] - centroids[j,:]
                d = np.linalg.norm(N, 2)
                Dist[j] = d
            dist, index = dminIndex(Dist, K)
            tags[i, index] = 1
        ## ȡֵ¾ĵ
        for i in range(K):
            ti = tags[:, i]
            st = sum(ti)
            if st != 0:
                # δֵֿ࣬Ϊһ
                for j in range(numOfAttr):
                    dj = data[:, j]
                    mp = ti * dj
                    sm = sum(mp)
                    centroids[i, j] = sm / st
            else:
                randidx = np.random.permutation(numOfData)
                centroids[i, :] = data[randidx[0], :]
                tags[randidx,:] = 0
                tags[randidx,i] = 1
        p_c = pre_centroids - centroids
        p = np.array(p_c, dtype=np.float64)
        n = np.linalg.norm(p_c.T, 2)
        if n < 0.001:
            break

    ##
    Distance = np.zeros((numOfData))
    Idx = np.zeros((numOfData), dtype=int)
    for i in range(numOfData):
        D = np.zeros((K))
        Dist = D
        # ÿ㵽ÿĵı׼
        for j in range(K):
            Dist[j] = np.linalg.norm(data[i, :] - centroids[j,:], 2)
        distance, idx = dminIndex(Dist, K)
        Distance[i] = distance
        Idx[i] = idx
    Distance = np.sum(Distance, 1-1)
    ## 
    return Idx, centroids, Distance

if __name__ == '__main__':
    #data = np.loadtxt('data.txt', dtype=np.float32, delimiter='\t')
    #centroid = np.loadtxt('centriod.txt', dtype=np.float32, delimiter='\t')
    #tag = np.loadtxt('tag1.txt', dtype=np.float32, delimiter=' ')
    # MyKMean(data, 5, centroid, 10)
    svd = np.loadtxt('svd1.txt', dtype=np.float32, delimiter='\t')
    u, s, coff = localSVD(svd)